﻿/*
https://leetcode.cn/problems/count-complete-tree-nodes/description/
222. 完全二叉树的节点个数
medium, 刘小康 2024.09.13
二分查找
*/

#include <iostream>
#include <bitset>

using namespace std;

/*
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
*/

class Solution
{
public:
    int tree_height(TreeNode* root)     // 测试通过
    {
        int height = 0;
        for (TreeNode* next = root; next != nullptr; next = next->left)
        {
            ++height;
        }
        return height;
    }

    int q_pow(int a, int n)     // 测试通过
    {
        if (n == 0)
        {
            return 1;
        }

        if (n == 1)
        {
            return a;
        }

        if (n & 1)  // 奇数
        {
            return q_pow(a, n - 1) * a;
        }
        else        // 偶数
        {
            int temp = q_pow(a, n >> 1);
            return temp * temp;
        }
    }

    // 判断指定叶子是否存在
    bool leaf_check(TreeNode* root, int n, int height)      // 叶子编号从 0 开始
    {
        bitset<32> temp(n);
        
        TreeNode* node = root;
        for (int i = height - 2; i >= 0; --i)
        {
            /*
            if (node == nullptr)
            {
                return false;
            }
            */

            // cout << "node " << node->val << endl;
            // cout << "temp[i] " << temp[i] << endl;
            if (temp[i])    // == 1
            {
                node = node->right;
            }
            else            // == 0
            {
                node = node->left;
            }

            /*
            if (node == nullptr)
            {
                cout << "node nullptr" << endl;
            }
            else
            {
                cout << "node " << node->val << endl;
            }
            */
        }

        if (node == nullptr)
        {
            return false;
        }
        // else
        return true;
    }

    int countNodes(TreeNode* root)
    {
        int height = tree_height(root);
        if (height == 0)
        {
            return 0;
        }
        if (height == 1)
        {
            return 1;
        }

        int leaf_count = q_pow(2, height - 1);

        int left = 0, right = leaf_count - 1;
        while (left < right)    // 上界
        {
            int mid = left + ((right + 1 - left) >> 1);
            // cout << "mid " << mid << endl;

            if (leaf_check(root, mid, height))
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
            // cout << "left: " << left << endl;
        }
        // cout << left;

        return q_pow(2, height - 1) + left;
    }
};
